package com.test.nodo;


import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 链表
 */
public class NoeReview {

    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Node(int value) {
            this.value = value;
        }
    }
    public static Node bulid(){
        Node node6 = new Node(5);
        Node node5 = new Node(4,node6);
        Node node4 = new Node(3,node5);
        Node node3 = new Node(3,node4);
        Node node2 = new Node(2,node3);
        Node node1 = new Node(1,node2);
        Node node0 = new Node(1,node1);
        return  node0;
    }
    public static void sys(Node head){
        while(head!=null){
            System.out.print(head.value+"\t");
            head = head.next;
        }
        System.out.println();
    }

    @Test
    public void test(){
        Node bulid = bulid();
        sys(bulid);
        Node bulid2 = bulid();
        Node node1 = mergeTwoLinked(bulid, bulid2);
        sys(node1);
//        Node node = deleteRepete(bulid);
//        sys(node);
    }
    /**
     * 反转单链表 循环
     * @return
     */
    public static Node reverseLoop(Node head){
        if(head==null || head.next==null){
            return head;
        }
        Node pre = null;
        while(head!=null){
            Node next = head.next;
            head.next  = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 反转单链表 递归
     * 1->  2-> 3-> 4
     * 4->3
     * head  next
     * 4->3->2->1
     * @return
     */
    public static Node reverse(Node head){
        if(head==null || head.next==null) {
            return head;
        }
        Node next = head.next;
        Node reverse = reverse(head.next); // head == 3 reverse = 4
        head.next = null;
        next.next = head;
        return reverse;
    }

    /**
     * 删除重复节点
     */
    public static Node deleteRepete(Node head){
        if(head == null || head.next==null){
            return head;
        }
        Node cur = head;
        Node pre = new Node(-1);
        Node newHead = pre;
        while(cur!=null){
            if(cur.next!=null&&cur.value==cur.next.value){
                while(cur.next!=null&&cur.value==cur.next.value){
                    cur = cur.next;
                }
                //第一个不一样的
                cur = cur.next;
                newHead.next = cur;

            }else {
                newHead.next = cur;
                newHead = cur;
                cur = cur.next;
            }
        }


        return pre.next;
    }

    /**
     * 1->2->3    -1->  1-> 1-> 2
     * 1->2->3              nexhead
     *       1->1->2->2->3
     *
     * 合并2个排序链表
     */
    public static Node mergeTwoLinked(Node node1,Node node2){
        if(node1==null || node2 == null){
            return node1==null?node2:node1;
        }
        Node newHead = new Node(-1);
        Node pre = newHead;
        Node node1Index = node1;
        Node node2Index = node2;
        while(node1Index!=null && node2Index!=null ){
            if(node1Index.value<=node2Index.value){
                newHead.next = node1Index;
                newHead = node1Index;
                node1Index = node1Index.next;
            }else {
                newHead.next = node2Index;
                newHead = node2Index;
                node2Index = node2Index.next;
            }
        }
        if(node1Index==null)  newHead.next = node2Index;
        if(node2Index==null)   newHead.next = node1Index;
        return  pre.next;
    }




//    /**
//     * 合并k个排序链表
//     */
//    public static Node sort(List<Node> nodeList){
//        PriorityQueue<Node> priorityQueue = new PriorityQueue(new Comparator<Node>() {
//            @Override
//            public int compare(Node o1, Node o2) {
//                return Integer.compare(o1.value,o2.value);
//            }
//        });
//
//    }





}
